# -*- coding: utf-8 -*-

'''
bucket.py
Created on Junho de 2013
@author: István Szapudi, http://www.ifa.hawaii.edu/~szapudi/astro735/lecture6/main.pdf

@compiled:
Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Bucket Sort"

Tempo de execução:
    Pior cenário O(N).

Bucket sort, ou bin sort, é um algoritmo de ordenação que funciona dividindo 
um vetor em um número finito de recipientes. Cada recipiente é então ordenado 
individualmente, seja usando um algoritmo de ordenação diferente, ou usando o 
algoritmo bucket sort recursivamente. O bucket sort tem complexidade linear 
O(n) quando o vetor volta a ser ordenado contém valores que são uniformemente
distribuídos.
    
    Carateristicas:
O primeiro e segundo ciclo têm uma complexidade O(N)
O terceiro ciclo, parece ser um ciclo encaixado: no entanto, o número total de 
objectos ainda é N, por conseguinte A.append (i) é executada N vezes.
Este algoritmo de ordenação é do tipo linear O(N).
Para N grande, pode ser melhor do que tipo algoritmos de comparação.

BIBLIOGRAFIA:
http://www.ifa.hawaii.edu/~szapudi/astro735/lecture6/main.pdf
http://pt.wikipedia.org/wiki/Bucket_sort

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    q = bucketSort([20,13,43,62,71,82,0,12,23,72,45,23,56,99])
    print q

RESULTADO:
[0, 12, 13, 20, 23, 23, 43, 45, 56, 62, 71, 72, 82, 99]
>>>

"""

import math

def bucketSort(A):
    """
    A is a list of positive integers between
    0...max
    """
    max = A[0]
    for number in A:
        if number > max:
            max = number
    
    bucket = [0]*(max+1)
    for number in A:
        bucket[number] += 1
    A = []
    for i in range(max+1):
        for j in range(bucket[i]):
            A.append(i)
    return A

def main():
    
    q = bucketSort([20,13,43,62,71,82,0,12,23,72,45,23,56,99])
    print q

if __name__ == '__main__':
    main()